import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2024-10-21
 * Time: 14:53
 */
public class test3 {
    /*
    LeetCode 46 全排列
    给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
     */

    //运用了回溯算法，第一点：先进行交换，之后利用完之后，再交换回来，这就是回溯
    //运用的容器：Collections，List，ArrayList

    public List<List<Integer>> permute(int[] nums) {
        List <List<Integer>> res = new ArrayList<List<Integer>>();

        List<Integer> output = new ArrayList<Integer>();

        for(int num:nums){
            output.add(num);
        }

        int n = nums.length;

        backtrack(n,output,res,0);
        return res;

    }

    public void backtrack(int n ,List<Integer> output,List<List<Integer>>res,int first){
        if(first==n){
            res.add(new ArrayList<Integer>(output));
        }

        for(int i = first;i<n;i++){
            Collections.swap(output,first,i);
            backtrack(n,output,res,first+1);
            Collections.swap(output,first,i);
        }
    }
}
